package maxSubArray

//最大子序和，使用动态规划
// 转移方程 dp[i] = max{dp[i]+dp[i-1],dp[i-1]}
//2,1,-3,4,-1,2,1,-5,4
func maxSubArray(nums []int) int {
	max := nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i-1] < 0 {
			nums[i] = nums[i]
		} else {
			nums[i] = nums[i] + nums[i-1]
		}
		//nums[i] = int(math.Max(float64(nums[i]+nums[i-1]), float64(nums[i])))
		if max < nums[i] {
			max = nums[i]
		}
	}
	return max
}
